Networks convey information about relationships between objects. Consequently, networks are used to model many kinds of information in fields ranging from communications and transportation to organizational and social network domains. Measuring distance or some other form of proximity or “closeness” in networks between two objects can be used as a data-mining tool. It may be applied directly to compare similarities between items, or within a more general scheme such as clustering and ordering. Moreover, measuring proximities may be useful to characterize the global structure of a network by showing the closeness of network components. For example, in a network with missing data, proximities may identify links that have been removed or cannot be observed. Proximities may also be used to find clusters, communities that behave similarly, etc.
In a network where links represent phone or email communications, proximity may measure potential information exchange between two non-linked objects through intermediaries. In a network where edges represent physical connections between machines, proximity may represent latency or speed of information exchange. In today's communication infrastructure, the speed of information exchange may be directly proportional to profits, as for example in the purchase and/or sale or stocks on the stock market.
Therefore, there is a need for a method and apparatus for measuring and extracting proximity in networks.